//实现标准库头文件<numeric>中accumulate函数的并行版本
#include <iostream>
#include <thread>
#include <numeric>
#include <algorithm>
#include <vector>
#include <functional>
#include <utility>
#include <windows.h>


using std::thread;
using std::vector;
using std::accumulate;
using std::cout;
using std::endl;

// 被执行的函数
template <typename Iterator, typename T> class Accum
{
public:
	void operator() (Iterator first, Iterator last, T &sum)
	{
		sum = 0;

		for (; first != last; ++first)
		{
			// 简单的计算素数
			auto k = std::sqrtf(*first);
			int i = 0;
			for (i = 2; i <= k; i++)
			{
				if ((*first)%i == 0)
				{
					break;
				}
			}

			if (i > k)
			{
				++sum;
			}
		}
	}
};

// 分发任务的函数
template <typename Iterator, typename T>
T ParallelAccum(Iterator first, Iterator last, T &sum)
{
	//计算迭代器中包含的元素数量
	const unsigned int len = std::distance(first, last);
	//若迭代器中没有元素则直接返回
	if (!len)
	{
		return sum;
	}

	//获取机器支持的并发线程数
	const unsigned int num_thread = thread::hardware_concurrency();

	//最终实际上每个线程处理的元素个数
	const unsigned int block_size = len / num_thread;
	//保存每个线程累加的结果
	vector<T> results(num_thread);
	//启动比num_thread - 1个线程，因为main函数本身已开启一个线程
	vector<thread> threads(num_thread - 1);

	//开始并行计算
	Iterator block_begin = first;
	for (unsigned int i = 0; i < (num_thread - 1); ++i)
	{
		Iterator block_end = block_begin;
		//将迭代器向前推进一个块,到达当前块的末尾位置
		std::advance(block_end, block_size);
		//传递参数,通常情况下thread的构造函数将复制所提供的参数,需要将模板参数转为引用
		threads[i] = thread(Accum<Iterator, T>(), block_begin, block_end, std::ref(results[i]));
		block_begin = block_end;
	}
	//处理最后一个线程,由于block_size = len / num_thread得到的结果不一定为整数,该线程处理剩余的所有元素
	Accum<Iterator, T>()(block_begin, last, results[num_thread - 1]);
	//对threads中所有线程调用join()
	std::for_each(threads.begin(), threads.end(), std::mem_fn(&thread::join));
	//
	return accumulate(results.begin(), results.end(), sum);
}

// 计时结构
LARGE_INTEGER t1, t2, tc;

void time_begin()
{
	QueryPerformanceFrequency(&tc);
	QueryPerformanceCounter(&t1);
}

float time_end()
{
	QueryPerformanceCounter(&t2);
	return ((t2.QuadPart - t1.QuadPart)*1.0 / tc.QuadPart) * 1000;
}

int main()
{
	// 装备任务队列
	vector<int> i_vec;
	int sum = 0;
	for (int i = 1; i != 501000; ++i)
	{
		i_vec.push_back(i);
	}

	// 并行计算示例
	time_begin();
	sum = ParallelAccum(i_vec.cbegin(), i_vec.cend(), sum);
	cout << "time: " << time_end() << ", sum = " << sum << endl;

	// 一般计算示例
	time_begin();
	Accum<vector<int>::iterator, int> a;
	a(i_vec.begin(), i_vec.end(), sum);
	cout << "time: " << time_end() << ", sum = " << sum << endl;


	return 0;
}
